﻿/*
*
*  Triangle-Triangle Overlap Test Routines
*  July, 2002
*  Updated December 2003
*  Ported to c# 2022
*
*  This file contains C implementation of algorithms for
*  performing two and three-dimensional triangle-triangle intersection test
*  The algorithms and underlying theory are described in
*
* "Fast and Robust Triangle-Triangle Overlap Test
*  Using Orientation Predicates"  P. Guigue - O. Devillers
*
*  Journal of Graphics Tools, 8(1), 2003
*
*  Several geometric predicates are defined.  Their parameters are all
*  points.  Each point is an array of two or three double precision
*  floating point numbers. The geometric predicates implemented in
*  this file are:
*
*    int tri_tri_overlap_test_3d(p1,q1,r1,p2,q2,r2)
*    int tri_tri_overlap_test_2d(p1,q1,r1,p2,q2,r2)
*
*    int tri_tri_intersection_test_3d(p1,q1,r1,p2,q2,r2,
*                                     coplanar,source,target)
*
*       is a version that computes the segment of intersection when
*       the triangles overlap (and are not coplanar)
*
*    each function returns 1 if the triangles (including their
*    boundary) intersect, otherwise 0
*
*
*  Other information are available from the Web page
*  http://www.acm.org/jgt/papers/GuigueDevillers03/
*
*/

namespace MatterHackers.PolygonMesh.Csg
{
    public static class TriangleIntersections
    {
        public static void CROSS(double[] dest, double[] v1, double[] v2)
        {
            dest[0] = v1[1] * v2[2] - v1[2] * v2[1];
            dest[1] = v1[2] * v2[0] - v1[0] * v2[2];
            dest[2] = v1[0] * v2[1] - v1[1] * v2[0];
        }

        public static double DOT(double[] v1, double[] v2)
        {
            return (v1[0] * v2[0] + v1[1] * v2[1] + v1[2] * v2[2]);
        }

        public static void SUB(double[] dest, double[] v1, double[] v2)
        {
            dest[0] = v1[0] - v2[0];
            dest[1] = v1[1] - v2[1];
            dest[2] = v1[2] - v2[2];
        }

        public static void SCALAR(double[] dest, double alpha, double[] v)
        {
            dest[0] = alpha * v[0];
            dest[1] = alpha * v[1];
            dest[2] = alpha * v[2];
        }

        public static int CHECK_MIN_MAX(double[] p1, double[] q1, double[] r1, double[] p2, double[] q2, double[] r2)
        {
            var v1 = new double[3];
            SUB(v1, p2, q1);
            var v2 = new double[3];
            SUB(v2, p1, q1);
            var N1 = new double[3];
            CROSS(N1, v1, v2);
            SUB(v1, q2, q1);
            if (DOT(v1, N1) > 0.0f)
            {
                return 0;
            }
            SUB(v1, p2, p1);
            SUB(v2, r1, p1);
            CROSS(N1, v1, v2);
            SUB(v1, r2, p1);
            if (DOT(v1, N1) > 0.0f)
            {
                return 0;
            }

            return 1;
        }

        /* Permutation in a canonical form of T2's vertices */
        public static int TRI_TRI_3D(double[] N1, double[] N2, double[] p1, double[] q1, double[] r1, double[] p2, double[] q2, double[] r2, double dp2, double dq2, double dr2)
        {
            if (dp2 > 0.0f)
            {
                if (dq2 > 0.0f)
                {
                    return CHECK_MIN_MAX(p1, r1, q1, r2, p2, q2);
                }
                else if (dr2 > 0.0f)
                {
                    return CHECK_MIN_MAX(p1, r1, q1, q2, r2, p2);
                }
                else
                {
                    return CHECK_MIN_MAX(p1, q1, r1, p2, q2, r2);
                }
            }
            else if (dp2 < 0.0f)
            {
                if (dq2 < 0.0f)
                {
                    return CHECK_MIN_MAX(p1, q1, r1, r2, p2, q2);
                }
                else if (dr2 < 0.0f)
                {
                    return CHECK_MIN_MAX(p1, q1, r1, q2, r2, p2);
                }
                else
                {
                    return CHECK_MIN_MAX(p1, r1, q1, p2, q2, r2);
                }
            }
            else
            {
                if (dq2 < 0.0f)
                {
                    if (dr2 >= 0.0f)
                    {
                        return CHECK_MIN_MAX(p1, r1, q1, q2, r2, p2);
                    }
                    else
                    {
                        return CHECK_MIN_MAX(p1, q1, r1, p2, q2, r2);
                    }
                }
                else if (dq2 > 0.0f)
                {
                    if (dr2 > 0.0f)
                    {
                        return CHECK_MIN_MAX(p1, r1, q1, p2, q2, r2);
                    }
                    else
                    {
                        return CHECK_MIN_MAX(p1, q1, r1, q2, r2, p2);
                    }
                }
                else
                {
                    if (dr2 > 0.0f)
                    {
                        return CHECK_MIN_MAX(p1, q1, r1, r2, p2, q2);
                    }
                    else if (dr2 < 0.0f)
                    {
                        return CHECK_MIN_MAX(p1, r1, q1, r2, p2, q2);
                    }
                    else
                    {
                        return coplanar_tri_tri3d(p1, q1, r1, p2, q2, r2, N1, N2);
                    }
                }
            }
        }

        // Three-dimensional Triangle-Triangle Overlap Test
        public static int tri_tri_overlap_test_3d(double[] N1, double[] N2, double[] p1, double[] q1, double[] r1, double[] p2, double[] q2, double[] r2)
        {
            double dp1, dq1, dr1, dp2, dq2, dr2;
            var v1 = new double[3];
            var v2 = new double[3];

            /* Compute distance signs  of p1, q1 and r1 to the plane of
               triangle(p2,q2,r2) */

            SUB(v1, p2, r2);
            SUB(v2, q2, r2);
            CROSS(N2, v1, v2);

            SUB(v1, p1, r2);
            dp1 = DOT(v1, N2);
            SUB(v1, q1, r2);
            dq1 = DOT(v1, N2);
            SUB(v1, r1, r2);
            dr1 = DOT(v1, N2);

            if (((dp1 * dq1) > 0.0f) && ((dp1 * dr1) > 0.0f))
            {
                return 0;
            }

            /* Compute distance signs  of p2, q2 and r2 to the plane of
               triangle(p1,q1,r1) */


            SUB(v1, q1, p1);
            SUB(v2, r1, p1);
            CROSS(N1, v1, v2);

            SUB(v1, p2, r1);
            dp2 = DOT(v1, N1);
            SUB(v1, q2, r1);
            dq2 = DOT(v1, N1);
            SUB(v1, r2, r1);
            dr2 = DOT(v1, N1);

            if (((dp2 * dq2) > 0.0f) && ((dp2 * dr2) > 0.0f)) return 0;

            /* Permutation in a canonical form of T1's vertices */


            if (dp1 > 0.0f)
            {
                if (dq1 > 0.0f) return TRI_TRI_3D(N1, N2, r1, p1, q1, p2, r2, q2, dp2, dr2, dq2);
                else if (dr1 > 0.0f) return TRI_TRI_3D(N1, N2, q1, r1, p1, p2, r2, q2, dp2, dr2, dq2);
                else return TRI_TRI_3D(N1, N2, p1, q1, r1, p2, q2, r2, dp2, dq2, dr2);
            }
            else if (dp1 < 0.0f)
            {
                if (dq1 < 0.0f) return TRI_TRI_3D(N1, N2, r1, p1, q1, p2, q2, r2, dp2, dq2, dr2);
                else if (dr1 < 0.0f) return TRI_TRI_3D(N1, N2, q1, r1, p1, p2, q2, r2, dp2, dq2, dr2);
                else return TRI_TRI_3D(N1, N2, p1, q1, r1, p2, r2, q2, dp2, dr2, dq2);
            }
            else
            {
                if (dq1 < 0.0f)
                {
                    if (dr1 >= 0.0f) return TRI_TRI_3D(N1, N2, q1, r1, p1, p2, r2, q2, dp2, dr2, dq2);
                    else return TRI_TRI_3D(N1, N2, p1, q1, r1, p2, q2, r2, dp2, dq2, dr2);
                }
                else if (dq1 > 0.0f)
                {
                    if (dr1 > 0.0f) return TRI_TRI_3D(N1, N2, p1, q1, r1, p2, r2, q2, dp2, dr2, dq2);
                    else return TRI_TRI_3D(N1, N2, q1, r1, p1, p2, q2, r2, dp2, dq2, dr2);
                }
                else
                {
                    if (dr1 > 0.0f) return TRI_TRI_3D(N1, N2, r1, p1, q1, p2, q2, r2, dp2, dq2, dr2);
                    else if (dr1 < 0.0f) return TRI_TRI_3D(N1, N2, r1, p1, q1, p2, r2, q2, dp2, dr2, dq2);
                    else return coplanar_tri_tri3d(p1, q1, r1, p2, q2, r2, N1, N2);
                }
            }
        }

        public static int coplanar_tri_tri3d(double[] p1, double[] q1, double[] r1,
                   double[] p2, double[] q2, double[] r2,
                   double[] normal_1, double[] normal_2)
        {

            var P1 = new double[2];
            var Q1 = new double[2];
            var R1 = new double[2];
            var P2 = new double[2];
            var Q2 = new double[2];
            var R2 = new double[2];

            double n_x, n_y, n_z;

            n_x = ((normal_1[0] < 0) ? -normal_1[0] : normal_1[0]);
            n_y = ((normal_1[1] < 0) ? -normal_1[1] : normal_1[1]);
            n_z = ((normal_1[2] < 0) ? -normal_1[2] : normal_1[2]);


            /* Projection of the triangles in 3D onto 2D such that the area of
               the projection is maximized. */


            if ((n_x > n_z) && (n_x >= n_y))
            {
                // Project onto plane YZ

                P1[0] = q1[2]; P1[1] = q1[1];
                Q1[0] = p1[2]; Q1[1] = p1[1];
                R1[0] = r1[2]; R1[1] = r1[1];

                P2[0] = q2[2]; P2[1] = q2[1];
                Q2[0] = p2[2]; Q2[1] = p2[1];
                R2[0] = r2[2]; R2[1] = r2[1];

            }
            else if ((n_y > n_z) && (n_y >= n_x))
            {
                // Project onto plane XZ

                P1[0] = q1[0]; P1[1] = q1[2];
                Q1[0] = p1[0]; Q1[1] = p1[2];
                R1[0] = r1[0]; R1[1] = r1[2];

                P2[0] = q2[0]; P2[1] = q2[2];
                Q2[0] = p2[0]; Q2[1] = p2[2];
                R2[0] = r2[0]; R2[1] = r2[2];

            }
            else
            {
                // Project onto plane XY

                P1[0] = p1[0]; P1[1] = p1[1];
                Q1[0] = q1[0]; Q1[1] = q1[1];
                R1[0] = r1[0]; R1[1] = r1[1];

                P2[0] = p2[0]; P2[1] = p2[1];
                Q2[0] = q2[0]; Q2[1] = q2[1];
                R2[0] = r2[0]; R2[1] = r2[1];
            }

            return tri_tri_overlap_test_2d(P1, Q1, R1, P2, Q2, R2);
        }



        /*
        *
        *  Three-dimensional Triangle-Triangle Intersection
        *
        */

        /*
           This macro is called when the triangles surely intersect
           It constructs the segment of intersection of the two triangles
           if they are not coplanar.
        */

        public static int CONSTRUCT_INTERSECTION(double[] target, double[] source, double[] N1, double[] N2, double[] p1, double[] q1, double[] r1, double[] p2, double[] q2, double[] r2)
        {
            var v1 = new double[3];
            SUB(v1, q1, p1);
            var v2 = new double[3];
            SUB(v2, r2, p1);
            var N = new double[3];
            CROSS(N, v1, v2);
            var v = new double[3];
            SUB(v, p2, p1);
            if (DOT(v, N) > 0.0f)
            {
                SUB(v1, r1, p1);
                CROSS(N, v1, v2);
                if (DOT(v, N) <= 0.0f)
                {
                    SUB(v2, q2, p1);
                    CROSS(N, v1, v2);
                    if (DOT(v, N) > 0.0f)
                    {
                        SUB(v1, p1, p2);
                        SUB(v2, p1, r1);
                        var alpha = DOT(v1, N2) / DOT(v2, N2);
                        SCALAR(v1, alpha, v2);
                        SUB(source, p1, v1);
                        SUB(v1, p2, p1);
                        SUB(v2, p2, r2);
                        alpha = DOT(v1, N1) / DOT(v2, N1);
                        SCALAR(v1, alpha, v2);
                        SUB(target, p2, v1);
                        return 1;
                    }
                    else
                    {
                        SUB(v1, p2, p1);
                        SUB(v2, p2, q2);
                        var alpha = DOT(v1, N1) / DOT(v2, N1);
                        SCALAR(v1, alpha, v2);
                        SUB(source, p2, v1);
                        SUB(v1, p2, p1);
                        SUB(v2, p2, r2);
                        alpha = DOT(v1, N1) / DOT(v2, N1);
                        SCALAR(v1, alpha, v2);
                        SUB(target, p2, v1);
                        return 1;
                    }
                }
                else
                {
                    return 0;
                }
            }
            else
            {
                SUB(v2, q2, p1);
                CROSS(N, v1, v2);
                if (DOT(v, N) < 0.0f)
                {
                    return 0;
                }
                else
                {
                    SUB(v1, r1, p1);
                    CROSS(N, v1, v2);
                    if (DOT(v, N) >= 0.0f)
                    {
                        SUB(v1, p1, p2);
                        SUB(v2, p1, r1);
                        var alpha = DOT(v1, N2) / DOT(v2, N2);
                        SCALAR(v1, alpha, v2);
                        SUB(source, p1, v1);
                        SUB(v1, p1, p2);
                        SUB(v2, p1, q1);
                        alpha = DOT(v1, N2) / DOT(v2, N2);
                        SCALAR(v1, alpha, v2);
                        SUB(target, p1, v1);
                        return 1;
                    }
                    else
                    {
                        SUB(v1, p2, p1);
                        SUB(v2, p2, q2);
                        var alpha = DOT(v1, N1) / DOT(v2, N1);
                        SCALAR(v1, alpha, v2);
                        SUB(source, p2, v1);
                        SUB(v1, p1, p2);
                        SUB(v2, p1, q1);
                        alpha = DOT(v1, N2) / DOT(v2, N2);
                        SCALAR(v1, alpha, v2);
                        SUB(target, p1, v1);
                        return 1;
                    }
                }
            }
        }



        public static int TRI_TRI_INTER_3D(double[] target, double[] source, double[] N1, double[] N2, double[] p1, double[] q1, double[] r1, double[] p2, double[] q2, double[] r2, double dp2, double dq2, double dr2, ref int coplanar)
        {
            if (dp2 > 0.0f)
            {
                if (dq2 > 0.0f) return CONSTRUCT_INTERSECTION(target, source, N1, N2, p1, r1, q1, r2, p2, q2);
                else if (dr2 > 0.0f) return CONSTRUCT_INTERSECTION(target, source, N1, N2, p1, r1, q1, q2, r2, p2);
                else return CONSTRUCT_INTERSECTION(target, source, N1, N2, p1, q1, r1, p2, q2, r2);
            }
            else if (dp2 < 0.0f)
            {
                if (dq2 < 0.0f) return CONSTRUCT_INTERSECTION(target, source, N1, N2, p1, q1, r1, r2, p2, q2);
                else if (dr2 < 0.0f) return CONSTRUCT_INTERSECTION(target, source, N1, N2, p1, q1, r1, q2, r2, p2);
                else return CONSTRUCT_INTERSECTION(target, source, N1, N2, p1, r1, q1, p2, q2, r2);
            }
            else
            {
                if (dq2 < 0.0f)
                {
                    if (dr2 >= 0.0f) return CONSTRUCT_INTERSECTION(target, source, N1, N2, p1, r1, q1, q2, r2, p2);
                    else return CONSTRUCT_INTERSECTION(target, source, N1, N2, p1, q1, r1, p2, q2, r2);
                }
                else if (dq2 > 0.0f)
                {
                    if (dr2 > 0.0f) return CONSTRUCT_INTERSECTION(target, source, N1, N2, p1, r1, q1, p2, q2, r2);
                    else return CONSTRUCT_INTERSECTION(target, source, N1, N2, p1, q1, r1, q2, r2, p2);
                }
                else
                {
                    if (dr2 > 0.0f) return CONSTRUCT_INTERSECTION(target, source, N1, N2, p1, q1, r1, r2, p2, q2);
                    else if (dr2 < 0.0f) return CONSTRUCT_INTERSECTION(target, source, N1, N2, p1, r1, q1, r2, p2, q2);
                    else
                    {
                        coplanar = 1;
                        return coplanar_tri_tri3d(p1, q1, r1, p2, q2, r2, N1, N2);
                    }
                }
            }
        }


        // Three-dimensional Triangle-Triangle Overlap Test
        // additionaly computes the segment of intersection of the two triangles if it exists.
        // coplanar returns whether the triangles are coplanar,
        // source and target are the endpoints of the line segment of intersection

        /*
           The following version computes the segment of intersection of the
           two triangles if it exists.
           coplanar returns whether the triangles are coplanar
           source and target are the endpoints of the line segment of intersection
        */

        public static int tri_tri_intersection_test_3d(double[] p1, double[] q1, double[] r1,
                 double[] p2, double[] q2, double[] r2,
                 ref int coplanar,
                 double[] source, double[] target)

        {
            double dp1, dq1, dr1, dp2, dq2, dr2;
            var v1 = new double[3];
            var v2 = new double[3];
            var v = new double[3];
            var N1 = new double[3];
            var N2 = new double[3];
            var N = new double[3];

            // Compute distance signs  of p1, q1 and r1
            // to the plane of triangle(p2,q2,r2)


            SUB(v1, p2, r2);
            SUB(v2, q2, r2);
            CROSS(N2, v1, v2);

            SUB(v1, p1, r2);
            dp1 = DOT(v1, N2);
            SUB(v1, q1, r2);
            dq1 = DOT(v1, N2);
            SUB(v1, r1, r2);
            dr1 = DOT(v1, N2);

            if (((dp1 * dq1) > 0.0f) && ((dp1 * dr1) > 0.0f)) return 0;

            // Compute distance signs  of p2, q2 and r2
            // to the plane of triangle(p1,q1,r1)


            SUB(v1, q1, p1);
            SUB(v2, r1, p1);
            CROSS(N1, v1, v2);

            SUB(v1, p2, r1);
            dp2 = DOT(v1, N1);
            SUB(v1, q2, r1);
            dq2 = DOT(v1, N1);
            SUB(v1, r2, r1);
            dr2 = DOT(v1, N1);

            if (((dp2 * dq2) > 0.0f) && ((dp2 * dr2) > 0.0f)) return 0;

            // Permutation in a canonical form of T1's vertices


            if (dp1 > 0.0f)
            {
                if (dq1 > 0.0f) return TRI_TRI_INTER_3D(target, source, N1, N2, r1, p1, q1, p2, r2, q2, dp2, dr2, dq2, ref coplanar);
                else if (dr1 > 0.0f) return TRI_TRI_INTER_3D(target, source, N1, N2, q1, r1, p1, p2, r2, q2, dp2, dr2, dq2, ref coplanar);


                else return TRI_TRI_INTER_3D(target, source, N1, N2, p1, q1, r1, p2, q2, r2, dp2, dq2, dr2, ref coplanar);
            }
            else if (dp1 < 0.0f)
            {
                if (dq1 < 0.0f) return TRI_TRI_INTER_3D(target, source, N1, N2, r1, p1, q1, p2, q2, r2, dp2, dq2, dr2, ref coplanar);
                else if (dr1 < 0.0f) return TRI_TRI_INTER_3D(target, source, N1, N2, q1, r1, p1, p2, q2, r2, dp2, dq2, dr2, ref coplanar);
                else return TRI_TRI_INTER_3D(target, source, N1, N2, p1, q1, r1, p2, r2, q2, dp2, dr2, dq2, ref coplanar);
            }
            else
            {
                if (dq1 < 0.0f)
                {
                    if (dr1 >= 0.0f) return TRI_TRI_INTER_3D(target, source, N1, N2, q1, r1, p1, p2, r2, q2, dp2, dr2, dq2, ref coplanar);
                    else return TRI_TRI_INTER_3D(target, source, N1, N2, p1, q1, r1, p2, q2, r2, dp2, dq2, dr2, ref coplanar);
                }
                else if (dq1 > 0.0f)
                {
                    if (dr1 > 0.0f) return TRI_TRI_INTER_3D(target, source, N1, N2, p1, q1, r1, p2, r2, q2, dp2, dr2, dq2, ref coplanar);
                    else return TRI_TRI_INTER_3D(target, source, N1, N2, q1, r1, p1, p2, q2, r2, dp2, dq2, dr2, ref coplanar);
                }
                else
                {
                    if (dr1 > 0.0f) return TRI_TRI_INTER_3D(target, source, N1, N2, r1, p1, q1, p2, q2, r2, dp2, dq2, dr2, ref coplanar);
                    else if (dr1 < 0.0f) return TRI_TRI_INTER_3D(target, source, N1, N2, r1, p1, q1, p2, r2, q2, dp2, dr2, dq2, ref coplanar);
                    else
                    {
                        // triangles are co-planar

                        coplanar = 1;
                        return coplanar_tri_tri3d(p1, q1, r1, p2, q2, r2, N1, N2);
                    }
                }
            }
        }

        /*
        *
        *  Two dimensional Triangle-Triangle Overlap Test
        *
        */


        /* some 2D macros */

        public static double ORIENT_2D(double[] a, double[] b, double[] c)
        {
            return ((a[0] - c[0]) * (b[1] - c[1]) - (a[1] - c[1]) * (b[0] - c[0]));
        }


        public static int INTERSECTION_TEST_VERTEX(double[] P1, double[] Q1, double[] R1, double[] P2, double[] Q2, double[] R2)
        {
            if (ORIENT_2D(R2, P2, Q1) >= 0.0f)
                if (ORIENT_2D(R2, Q2, Q1) <= 0.0f)
                    if (ORIENT_2D(P1, P2, Q1) > 0.0f)
                    {
                        if (ORIENT_2D(P1, Q2, Q1) <= 0.0f) return 1;
                        else return 0;
                    }
                    else
                    {
                        if (ORIENT_2D(P1, P2, R1) >= 0.0f)
                            if (ORIENT_2D(Q1, R1, P2) >= 0.0f) return 1;
                            else return 0;
                        else return 0;
                    }
                else
                  if (ORIENT_2D(P1, Q2, Q1) <= 0.0f)
                    if (ORIENT_2D(R2, Q2, R1) <= 0.0f)
                        if (ORIENT_2D(Q1, R1, Q2) >= 0.0f) return 1;
                        else return 0;
                    else return 0;
                else return 0;
            else
                if (ORIENT_2D(R2, P2, R1) >= 0.0f)
                if (ORIENT_2D(Q1, R1, R2) >= 0.0f)
                    if (ORIENT_2D(P1, P2, R1) >= 0.0f) return 1;
                    else return 0;
                else
            if (ORIENT_2D(Q1, R1, Q2) >= 0.0f)
                {
                    if (ORIENT_2D(R2, R1, Q2) >= 0.0f) return 1;
                    else return 0;
                }
                else return 0;
            else return 0;
        }



        public static int INTERSECTION_TEST_EDGE(double[] P1, double[] Q1, double[] R1, double[] P2, double[] Q2, double[] R2)
        {
            if (ORIENT_2D(R2, P2, Q1) >= 0.0f)
            {
                if (ORIENT_2D(P1, P2, Q1) >= 0.0f)
                {
                    if (ORIENT_2D(P1, Q1, R2) >= 0.0f) return 1;
                    else return 0;
                }
                else
                {
                    if (ORIENT_2D(Q1, R1, P2) >= 0.0f)
                    {
                        if (ORIENT_2D(R1, P1, P2) >= 0.0f) return 1; else return 0;
                    }
                    else return 0;
                }
            }
            else
            {
                if (ORIENT_2D(R2, P2, R1) >= 0.0f)
                {
                    if (ORIENT_2D(P1, P2, R1) >= 0.0f)
                    {
                        if (ORIENT_2D(P1, R1, R2) >= 0.0f) return 1;
                        else
                        {
                            if (ORIENT_2D(Q1, R1, R2) >= 0.0f) return 1; else return 0;
                        }
                    }
                    else return 0;
                }
                else return 0;
            }
        }



        public static int ccw_tri_tri_intersection_2d(double[] p1, double[] q1, double[] r1,
                double[] p2, double[] q2, double[] r2)
        {
            if (ORIENT_2D(p2, q2, p1) >= 0.0f)
            {
                if (ORIENT_2D(q2, r2, p1) >= 0.0f)
                {
                    if (ORIENT_2D(r2, p2, p1) >= 0.0f) return 1;
                    else return INTERSECTION_TEST_EDGE(p1, q1, r1, p2, q2, r2);
                }
                else
                {
                    if (ORIENT_2D(r2, p2, p1) >= 0.0f)
                        return INTERSECTION_TEST_EDGE(p1, q1, r1, r2, p2, q2);
                    else return INTERSECTION_TEST_VERTEX(p1, q1, r1, p2, q2, r2);
                }
            }
            else
            {
                if (ORIENT_2D(q2, r2, p1) >= 0.0f)
                {
                    if (ORIENT_2D(r2, p2, p1) >= 0.0f)
                        return INTERSECTION_TEST_EDGE(p1, q1, r1, q2, r2, p2);
                    else return INTERSECTION_TEST_VERTEX(p1, q1, r1, q2, r2, p2);
                }
                else return INTERSECTION_TEST_VERTEX(p1, q1, r1, r2, p2, q2);
            }
        }


        // Two dimensional Triangle-Triangle Overlap Test

        public static int tri_tri_overlap_test_2d(double[] p1, double[] q1, double[] r1,
                  double[] p2, double[] q2, double[] r2)
        {
            if (ORIENT_2D(p1, q1, r1) < 0.0f)
                if (ORIENT_2D(p2, q2, r2) < 0.0f)
                    return ccw_tri_tri_intersection_2d(p1, r1, q1, p2, r2, q2);
                else
                    return ccw_tri_tri_intersection_2d(p1, r1, q1, p2, q2, r2);
            else
              if (ORIENT_2D(p2, q2, r2) < 0.0f)
                return ccw_tri_tri_intersection_2d(p1, q1, r1, p2, r2, q2);
            else
                return ccw_tri_tri_intersection_2d(p1, q1, r1, p2, q2, r2);

        }
    }
}
